import java.util.*;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2020/4/19 上午 10:36
 */
public class month2004 {

    public static String reformat(String s) {
        if (s.length() == 1) {
            return s;
        }
        int length = s.length();
        char[] chars = s.toCharArray();
        int charNum = 0;
        int numNum = 0;
        char[] charArr = new char[length / 2 + 1];
        char[] numArr = new char[length / 2 + 1];
        StringBuilder builder = new StringBuilder();
        for (char aChar : chars) {
            if (Character.isDigit(aChar)) {
                numArr[numNum] = aChar;
                numNum++;
            } else {
                charArr[charNum] = aChar;
                charNum++;
            }
        }
        if (charNum > numNum) {
            if (charNum - numNum != 1) {
                return "";
            }
            while (charNum >= 0) {
                builder.append(charArr[charNum]);
                if (numNum >= 0) {
                    builder.append(numArr[numNum]);
                }
                charNum--;
                numNum--;
            }
        } else if (numNum > charNum) {
            if (numNum - charNum != 1) {
                return "";
            }
            while (numNum >= 0) {
                builder.append(numArr[numNum]);
                if (charNum >= 0) {
                    builder.append(charArr[charNum]);
                }
                charNum--;
                numNum--;
            }
        } else {
            while (numNum >= 0) {
                builder.append(numArr[numNum]);
                builder.append(charArr[charNum]);
                charNum--;
                numNum--;
            }
        }
        return builder.toString().replaceAll(" ", "");
    }


    public List<List<String>> displayTable(List<List<String>> orders) {
        List<List<String>> res = new ArrayList<>();
        Map<String, Integer> foodMap = new TreeMap<>();
        Map<Integer, List<Integer>> tableMap = new TreeMap<>();
        int countNum = 0;
        for (List<String> order : orders) {
            int tableNum = Integer.parseInt(order.get(1));
            String foodItem = order.get(2);
            int itemNumber;
            if (foodMap.containsKey(foodItem)) {
                itemNumber = foodMap.get(foodItem);
            } else {
                foodMap.put(foodItem, countNum);
                itemNumber = countNum;
                countNum++;
            }
            if (tableMap.containsKey(tableNum)) {
                List<Integer> table = tableMap.get(tableNum);
                table.add(itemNumber);
                tableMap.put(tableNum, table);
            } else {
                List<Integer> table = new ArrayList<>();
                table.add(itemNumber);
                tableMap.put(tableNum, table);
            }
        }
        List<String> oneRow = new ArrayList<>();
        oneRow.add("Table");
        for (Map.Entry<String, Integer> entry : foodMap.entrySet()) {
            String key = entry.getKey();
            oneRow.add(key);
        }
        res.add(oneRow);
        oneRow.clear();
        for (Map.Entry<Integer, List<Integer>> entry : tableMap.entrySet()) {
            Integer tableNum = entry.getKey();
            List<Integer> table = entry.getValue();
            oneRow.add(String.valueOf(tableNum));
            Map<Integer, Integer> menu = new TreeMap<>();
            for (Integer t : table) {
                if (menu.containsKey(t)) {
                    menu.put(t, menu.get(t) + 1);
                } else {
                    menu.put(t, 1);
                }
            }
            for (Map.Entry<String, Integer> e : foodMap.entrySet()) {
                Integer foodNum = e.getValue();
                if (menu.containsKey(foodNum)) {
                    Integer menuNum = menu.get(foodNum);
                    oneRow.add(String.valueOf(menuNum));
                } else {
                    oneRow.add("0");
                }
            }
            res.add(oneRow);
            oneRow.clear();
        }
        return res;
    }

    public int minNumberOfFrogs(String croakOfFrogs) {
        int[] countFrog = new int[5];
        int max = 0;
        int cur = 0;
        for (int i = 0; i < croakOfFrogs.length(); i++) {
            char charAt = croakOfFrogs.charAt(i);
            int index = getIndex(charAt);
            if (index == -1) {
                return -1;
            }
            if (index == 0) {
                countFrog[0]++;
                cur++;
                max = Math.max(max, cur);
            } else {
                if (countFrog[index - 1] == 0) {
                    return -1;
                }
                countFrog[index - 1]--;
                if (index == 4) {
                    cur--;
                } else {
                    countFrog[index]++;
                }
            }
        }
        return cur == 0 ? max : -1;
    }

    private int getIndex(char ch) {
        if (ch == 'c') {
            return 0;
        } else if (ch == 'r') {
            return 1;
        } else if (ch == 'o') {
            return 2;
        } else if (ch == 'a') {
            return 3;
        } else if (ch == 'k') {
            return 4;
        }
        return -1;
    }


    //按要求生成一个n长度的array，每个元素1<=x<=m，最后比对大小的结果是k次，
    //也就是说有k-1次情况后面的数比前面的大
    //显然k > n 不行，m < k 也不行，所以必须 n, m >= k
    //一种是增长，只能k-1个数
    //一种是浮动，后面的更小就行
    //看着数据量是穷举的套路，其实对于每种nmk，后面几个大的数只和当前数，以及剩余的个数有关，也可以backtracking的
    private final int mod = 1_000_000_007;
    private Long[][][] cache;

    public int numOfArrays(int n, int m, int k) {
        if (n < k || m < k) {
            return 0;
        }
        cache = new Long[n + 1][k + 1][m + 1];
        long res = 0;
        //设置第0号
        for (int i = 1; i <= m; i++) {
            res = (res + dfs(n - 1, i, m, k - 1)) % mod;
        }
        return (int) res;
    }

    private long dfs(int n, int max, int m, int k) {
        if (k < 0) {
            return 0;
        }
        if (n == 0) {
            if (k == 0) {
                return 1;
            } else {
                return 0;
            }
        }
        //cache
        if (cache[n][k][max] != null) {
            return cache[n][k][max];
        }
        long res = 0;
        for (int i = 1; i <= m; i++) {
            if (i > max) {
                res = (res + dfs(n - 1, i, m, k - 1)) % mod;
            } else {
                res = (res + dfs(n - 1, max, m, k)) % mod;
            }
        }
        cache[n][k][max] = res;
        return res;
    }


    public int expectNumber(int[] scores) {
        HashSet<Integer> set = new HashSet<>();
        for (int score : scores) {
            set.add(score);
        }
        return set.size();
    }


    public static void main(String[] args) {
        month2004 month2004 = new month2004();

//        System.out.println(reformat("a0b1c2"));
    }
}
